1. Field of the Invention
The present invention relates generally to surface parameterizations, and in particular, to a method, apparatus, and article of manufacture for matching surfaces.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
The body of relevant literature is quite broad due to the wide span of fields in which parameterizations are studied. Most relevant to our treatment of parameterizations on triangulated surfaces is the graphics literature. In the context of correspondences between surfaces, work in image matching may be reviewed. In particular the non-linear approaches that deal directly with the large deformation setting. Relevant work from the graphics literature covers approaches which pursue direct mappings between surfaces in 3.
Parameterization
The most desirable property to achieve in a parameterization is isometry. This implies intuitively that all of the properties of the surface are represented in the corresponding parameter domain.
Strictly speaking, a map between two surfaces is an isometry if their first fundamental forms coincide. It is well known that isometric parameterizations exist only if the surface itself is locally flat, i.e. developable. A broad variety of algorithms have been proposed to construct such parameterizations for embedded triangle meshes (for a recent survey see the comprehensive overview by Floater and Hormann [19]). Generically these algorithms are distinguished by the way they measure distortion.
Distortion is a measurement of change in the first fundamental form of the mapping between the surface and the parameter domain, i.e., how much the metric induced by the parameterization deviates from the identity. There are many possible ways to measure deviation from the identity.
For example, Sander et al. consider the minimization of a variety of norms (l2, l∞) of the singular values of the Jacobian [44], while Hormann and Greiner minimize the condition number of the Jacobian [25]. Degener et al. extend this work by adding a term that penalizes area distortion [14].
The maximum eigenvalue of the Jacobian and its inverse were used by Sorkine et al. [47]. These approaches all involve difficult algorithms and it is unclear what guarantees can be made of the resulting parameterizations.
Other free-boundary methods are primarily concerned with controlling angle distortion. On one hand we find methods which attempt to construct conformal parameterizations directly. These include the minimization of harmonic energy with natural boundary conditions [15], which turns out to be equivalent to a least-squares optimal discrete approximation of conformal parameterizations [29]. The case of closed, arbitrary genus surfaces (possibly after constructing a double cover) was treated by Gu and Yau [24] based on discrete Riemann surface theory [33]. Direct minimization of the change of angle was pursued by Sheffer and de Sturler [46], who used a highly non-linear minimization procedure. Kharevych et al. approached discrete conformal parameterizations by deriving a convex energy based on the intersection angles of circles on the surface triangulation [26]. In this class of methods the focus is entirely on controlling angle distortion, with the exception of Desbrun et al. who also define a separate authalic energy to control the change of area (although only in the presence of Dirichlet boundary conditions).
In all of these approaches, the interaction between area, angle and length distortion is not easily controlled or well understood from a mathematical perspective, e.g., little is known about the existence of solutions. With the exception of methods based on harmonic or conformal maps [15, 24, 26, 29], most of the previous work is formulated in the discrete setting of surface triangulations where these results are unknown.
Image Matching
In image processing, registration is often approached as a variational problem. One asks for a deformation that maps structures in the reference image A onto corresponding structures in the template image B on some image domain ω. In the case of unimodal images with a direct correspondence of the image intensities IA and IB, the energy ∫107(IB(ξ)−IA(φ(ξ))2 dξ measures the least-squares error of the match. We extend this idea to surface matching through a bending energy that measures the matching defect with respect to curvatures. It is well established that the associated minimization problem is ill-posed if one considers the infinite dimensional space of deformations [7, 48]. This is generally addressed by choosing a suitable regularization. Motivated by models from continuum mechanics, one may ask for a deformation that is additionally controlled by elastic stresses on images regarded as elastic sheets. For example see the early work of Bajcsy and Broit [3] and significant extensions by Grenander and Miller [20]. In the present invention relating to surface matching, we consider surfaces as thin shells. Besides the bending which we mentioned, surface deformations also lead to tangential stretching and shearing, which gives a real physical interpretation to the elastic stresses that are treated as a regularization in the resulting model. In particular, if large displacements are necessary to ensure a proper match, a regularization based on non-linear elasticity with its built-in control of length, area and volume changes is indispensible. Cohen [11] considered polyconvex elastic functionals and Droske and Rumpf [18] used this type of regularization to guarantee global injectivity and well-posedness. Such concepts may be used to avoid folding in our surface matches. In essence, non-rigid image matching is a powerful tool that may be used for surface matching.
3D Registration and Correspondence
Motivated by the ability to scan geometry with high fidelity, a number of approaches have been developed in the graphics literature to bring such scans into correspondence. Early work used parameterizations of the meshes over a common parameter domain to establish a direct correspondence between them [28]. Typically these methods are driven by user-supplied feature correspondences which are then used to drive a mutual parameterization. The main difficulty is the management of the proper alignment of selected features during the parameterization process [27, 43, 45] and the algorithmic issues associated with the management of irregular meshes and their effective overlay.
Special methods have been developed for situations in which a large number of scans of similar objects, albeit with great geometric variety, are to be brought into correspondence, for example for purposes of statistical analysis. These are typically geared towards establishing a correspondence against a template model. Blanz and Vetter [5] used cylindrical scans resulting in height “images” which were matched through a modified optical flow. Allen et al. [1] fit a high resolution template mesh to scans of the human body. They computed non-rigid deformations for the template by minimizing an error functional which performs well in the presence of holes and poorly sampled data, provided that the two surfaces are in similar poses. Such template-based approaches can also be very helpful during the acquisition itself. Zhang et al. [50] present a method for meshing dynamic range data using a surface fitting approach. In their method, a template mesh is fitted to a registered stereo pair of depth maps and the fitting is achieved by minimizing a depth matching energy and a regularization energy. Recently, Gu and Vemuri [23] considered matches of topological spheres through conformal maps with applications to brain matching. Their energy measures the defect of the conformal factor and—similar to the approach of the invention—the defect of the mean curvature. However they do not measure the correspondence of feature sets or tangential distortion, and thus do not involve a regularization energy for the ill-posed energy minimization. Furthermore, they seek a one-to-one correspondence, whereas the present invention must address the difficult problem of partial correspondences between surfaces with boundaries.